# Python中表示图的几种常见方法

"""
在计算机科学中，图是由节点（顶点）和边组成的数据结构。
Python中有多种方式可以表示图结构，每种方式都有其优缺点。
本文件展示了四种常见的图表示方法：
1. 邻接矩阵
2. 邻接表
3. 边列表
4. 使用NetworkX库
"""

# 示例图：
# A --- B
# |     |
# |     |
# C --- D

# 1. 邻接矩阵表示法
# 优点：查询两点是否相连的时间复杂度为O(1)
# 缺点：空间复杂度为O(V²)，对于稀疏图来说浪费空间
print("1. 邻接矩阵表示法")
adjacency_matrix = [
    [0, 1, 1, 0],  # A与B、C相连
    [1, 0, 0, 1],  # B与A、D相连
    [1, 0, 0, 1],  # C与A、D相连
    [0, 1, 1, 0]   # D与B、C相连
]

# 节点映射（便于理解）
nodes = ['A', 'B', 'C', 'D']

# 检查两个节点是否相连
def is_connected_matrix(node1, node2):
    idx1 = nodes.index(node1)
    idx2 = nodes.index(node2)
    return adjacency_matrix[idx1][idx2] == 1

print(f"A和B是否相连: {is_connected_matrix('A', 'B')}")
print(f"A和D是否相连: {is_connected_matrix('A', 'D')}")
print()

# 2. 邻接表表示法
# 优点：空间复杂度为O(V+E)，适合稀疏图
# 缺点：查询两点是否相连的时间复杂度为O(V)
print("2. 邻接表表示法")
adjacency_list = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# 检查两个节点是否相连
def is_connected_list(node1, node2):
    return node2 in adjacency_list[node1]

print(f"A和B是否相连: {is_connected_list('A', 'B')}")
print(f"A和D是否相连: {is_connected_list('A', 'D')}")
print()

# 3. 边列表表示法
# 优点：简单直观，适合某些算法
# 缺点：查询操作效率低
print("3. 边列表表示法")
edge_list = [
    ('A', 'B'),
    ('A', 'C'),
    ('B', 'D'),
    ('C', 'D')
]

# 检查两个节点是否相连
def is_connected_edge_list(node1, node2):
    return (node1, node2) in edge_list or (node2, node1) in edge_list

print(f"A和B是否相连: {is_connected_edge_list('A', 'B')}")
print(f"A和D是否相连: {is_connected_edge_list('A', 'D')}")
print()

# 4. 使用NetworkX库
# 优点：功能丰富，易于使用，提供多种图算法
# 缺点：需要安装额外的库
print("4. 使用NetworkX库")
try:
    import networkx as nx
    import matplotlib.pyplot as plt
    
    # 创建无向图
    G = nx.Graph()
    
    # 添加节点
    G.add_nodes_from(['A', 'B', 'C', 'D'])
    
    # 添加边
    G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')])
    
    # 检查两个节点是否相连
    print(f"A和B是否相连: {nx.has_path(G, 'A', 'B')}")
    print(f"A和D是否相连: {nx.has_path(G, 'A', 'D')}")
    
    # 可视化图
    print("如果要可视化图，可以使用以下代码：")
    print("nx.draw(G, with_labels=True)")
    print("plt.show()")
    
except ImportError:
    print("请安装NetworkX库以使用此功能：pip install networkx matplotlib")

# 5. 使用类来表示图
print("\n5. 使用类来表示图")
class Graph:
    def __init__(self):
        self.graph = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.graph:
            if vertex2 not in self.graph[vertex1]:
                self.graph[vertex1].append(vertex2)
        else:
            self.graph[vertex1] = [vertex2]
        
        # 对于无向图，需要添加反向边
        if vertex2 in self.graph:
            if vertex1 not in self.graph[vertex2]:
                self.graph[vertex2].append(vertex1)
        else:
            self.graph[vertex2] = [vertex1]
    
    def is_connected(self, vertex1, vertex2):
        return vertex1 in self.graph and vertex2 in self.graph[vertex1]
    
    def display(self):
        for vertex, neighbors in self.graph.items():
            print(f"{vertex}: {neighbors}")

# 创建图实例
g = Graph()
for vertex in ['A', 'B', 'C', 'D']:
    g.add_vertex(vertex)

g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')

print("图的结构：")
g.display()
print(f"A和B是否相连: {g.is_connected('A', 'B')}")
print(f"A和D是否相连: {g.is_connected('A', 'D')}")

# 6. 加权图表示
print("\n6. 加权图表示")
weighted_adjacency_list = {
    'A': [('B', 5), ('C', 3)],
    'B': [('A', 5), ('D', 2)],
    'C': [('A', 3), ('D', 8)],
    'D': [('B', 2), ('C', 8)]
}

print("加权邻接表：")
for vertex, edges in weighted_adjacency_list.items():
    print(f"{vertex}: {edges}")

# 加权邻接矩阵
weighted_matrix = [
    [0, 5, 3, 0],  # A到其他节点的权重
    [5, 0, 0, 2],  # B到其他节点的权重
    [3, 0, 0, 8],  # C到其他节点的权重
    [0, 2, 8, 0]   # D到其他节点的权重
]

print("\n加权邻接矩阵：")
for i, row in enumerate(weighted_matrix):
    print(f"{nodes[i]}: {row}")